/*
 **********************************************************
 *
 * Programme :	graphe.c
 *
 * ecrit par :	BAYRAMOV Matin & IBRAHIMLI Nihat
 *
 * resume 	 :  contient les fonctions utiles
 * 				pour la manupilation des graphes
 *
 * date :   		Feb 6, 2013
 *
 ***********************************************************
 */

#include <stdio.h>
#include <stdlib.h>

#include <unistd.h>
#include <math.h>

#include "stack.h"
#include "graphe.h"


int * vertexColor = NULL;
int * vertexFather = NULL;

/*******************************************************************
 *
 * Fonction 	: 	creation
 *
 * Parametres 	: 	Graphe** graphe (le pointeur sur le graphe)
 * 					int nbSommet (le nombre maximum de sommets)
 *
 * Retour 		:	GRAPHE_DEJA_EXISTANT si le graphe existe deja ou pas
 * 					MAX_SOMMET_INVALIDE si le nombre maximum de sommets n'est pas valide
 * 					PROBLEME_MEMOIRE  si l'allocation est échoue
 * 					RES_OK si le resultat est OK
 *
 * Description 	: 	fonction crée un graphe graphe de "nbSommet" sommets,
 * 					alloue la mémoire pour les listes d'adjacances, elle les initialise à NULL
 *
 *
 * Complexité	:	O(n) - n le nombre de max de sommets
 *
 */

int creation(Graphe** graphe, int nbSommet) {

	// Verification de l'existance de graphe
	if ((*graphe) != NULL) {
		return GRAPHE_DEJA_EXISTANT;
	}

	// Si le nombre max de sommet n'est pas valide
	if (nbSommet <= 0) {
		return MAX_SOMMET_INVALIDE;
	}

	// Allocation mémoire pour un graphe
	(*graphe) = (Graphe *) malloc (sizeof(Graphe));

	// Vérification de l'allocation mémoire
	if ((*graphe) == NULL) {
		return PROBLEME_MEMOIRE;
	}

	// Allocation mémoire
	(*graphe)->nbMaxSommets = nbSommet;
	(*graphe)->listesAdjacences = NULL;

	(*graphe)->listesAdjacences = (TypVoisins**) malloc(
			(*graphe)->nbMaxSommets * sizeof(TypVoisins*));

	// Vérification de l'allocation mémoire
	if ((*graphe)->listesAdjacences == NULL) {
		return PROBLEME_MEMOIRE;
	}

	int i;
	// Initialisation à NULL
	for (i = 0; i < nbSommet; i++) {
		(*graphe)->listesAdjacences[i] = NULL;
	}

	return RES_OK;
}

/*******************************************************************
 *
 * Fonction 	: 	insertionSommet
 *
 * Parametres 	: 	Graphe* graphe (le pointeur sur le graphe)
 * 					int sommet (un sommet)
 *
 * Retour 		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 					SOMMET_INVALIDE si le sommet n'est pas correct
 * 					SOMMET_DEJA_EXISTANT si le sommet existe déjà
 * 					RES_OK si le resultat est OK
 *
 * Description 	: 	fonction insere le sommet "sommet-1" dans le graphe graphe
 *
 *
 * Complexité	:	O(1) 
 *
 */

int insertionSommet(Graphe* graphe, int sommet) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graphe);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	// Verification de graphe et le sommet
	result = sommetEstValide(graphe->nbMaxSommets, sommet);
	if (result != RES_OK) { return result; }

	// Si le sommet n'est pas encore crée
	if (graphe->listesAdjacences[sommet - 1] != NULL) {
		return SOMMET_DEJA_EXISTANT;
	}

	// On crée le nouvel sommet
	result = createListElement(&(graphe->listesAdjacences[sommet - 1]), -1, 0);

	// Verification de la création
	return (result != RES_OK) ? result : RES_OK;
}


// Insert next vertex into the graph and return it's index
int insertNextVertex(Graphe* graph) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graph);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	int var;
	for (var = 0; var < graph->nbMaxSommets; var++) {
		// A vertex not added
		if (graph->listesAdjacences[var] == NULL) {

			// Add it
			insertionSommet(graph, var+1);

			// Return it's index
			return  var;
		}
	}

	return RES_OK;
}
/*******************************************************************
 *
 * Fonction 	: 	insertionArete
 *
 * Parametres 	: 	Graphe* graphe - le pointeur sur le graphe
 * 					int somCourant - le sommet courant
 *					int somVoisin - le sommet voisin
 *					double poids - le poids de l'arete
 *					char o - si l'arete est orientée ou non orientée
 *
 * Retour 		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 					SOMMET_INVALIDE si un des sommets n'est pas correct
 * 					SOMMET_INEXISTANT si un des sommets n'existe pas
 *					POIDS_INVALIDE si le poids de l'arete n'est pas correct
 * 					RES_OK si le resultat est OK
 *
 * Description 	: 	fonction insere une arete du sommet "somDep-1" au
 *					sommet "somArr-1" avec un poids de "poids" dans le graphe graphe
 *
 *
 * Complexité	:	O(1) 
 *
 */

int insertionArete(Graphe* graphe, int somCourant, int somVoisin, double poids, char o) {

	int result = 0;

	// Verification de graphe
	result = grapheEstValide(graphe);
	if (result != RES_OK) { return result; }

	// Vérification de l'existance du sommet
	result = sommetEstExist(graphe, somCourant);
	if (result != RES_OK) { return result; }

	// Vérification de l'existance du sommet
	result = sommetEstExist(graphe, somVoisin);
	if (result != RES_OK) { return result; }

	// Vérification du poids
	result = poidsEstValide(poids);
	if (result != RES_OK) { return result; }

	// Vérification de type de l'arete
	result = typeAreteValide(o);
	if (result != RES_OK) { return result; }

	result = addBeginningElement(&(graphe->listesAdjacences[somCourant - 1]),
			somVoisin - 1, poids);
	if (result != RES_OK) { return result; }

	// S'il s'agit d'une arete non-orientée
	if (o == 'n') {
		result = addBeginningElement(&(graphe->listesAdjacences[somVoisin - 1]),
				somCourant - 1, poids);
		if (result != RES_OK) { return result; }
	}

	return RES_OK;
}

/*******************************************************************
 *
 * Fonction 	: 	suppressionSommet
 *
 * Parametres 	: 	Graphe* graphe (le pointeur sur le graphe)
 * 					int sommet (un sommet)
 *
 * Retour 		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 					SOMMET_INVALIDE si le sommet n'est pas correct
 *					SOMMET_INEXISTANT si le sommet n'existe pas
 * 					RES_OK si le resultat est OK
 *
 * Description 	: 	fonction supprime le sommet "sommet-1" et
 * 					toutes les aretes avec "sommet-1" dans le graphe graphe
 *
 *
 * Complexité	:	O(n) - n nombre max de sommets
 *
 */

int suppressionSommet(Graphe* graphe, int sommet) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graphe);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	// Verification de graphe et le sommet
	result = sommetEstValide(graphe->nbMaxSommets, sommet);
	if (result != RES_OK) { return result; }

	// Vérification de l'existance du sommet
	result = sommetEstExist(graphe, sommet);
	if (result != RES_OK) { return result; }

	// On supprime tout les aretes
	result = freeListe(&(graphe->listesAdjacences[sommet - 1]));
	if (result != RES_OK) { return result; }

	graphe->listesAdjacences[sommet - 1] = NULL;

	int i;

	// On parcours tout le graphe
	for (i = 0; i < graphe->nbMaxSommets; i++) {

		if (graphe->listesAdjacences[i] != NULL) {

			// On supprime tout les aretes concernant ce sommet
			result = removeElement(&(graphe->listesAdjacences[i]), sommet - 1);
		}
	}

	return RES_OK;
}

/*******************************************************************
 *
 * Fonction 	: 	suppressionArete
 *
 * Parametres 	: 	Graphe* graphe - le pointeur sur le graphe
 * 					int somCourant - le sommet courant
 *					int somVoisin - le sommet voisin
 *					char o - si l'arete est orientée ou non orientée
 *
 * Retour 		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 					SOMMET_INVALIDE si un des sommets n'est pas correct
 *					SOMMET_INEXISTANT si un des sommets n'existe pas
 *					TYPE_ARETE_INVALID si le type d'arete n'est pas bon
 * 					RES_OK si le resultat est OK
 *
 * Description 	: 	fonction supprime une arete entre le sommetCourant
 * 					et sommetVoisin
 *
 *
 * Complexité	:	O(1) 
 *
 */

int suppressionArete(Graphe* graphe, int somCourant, int somVoisin, char o) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graphe);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	// Vérification de l'existance du sommet
	result = sommetEstExist(graphe, somCourant);
	if (result != RES_OK) { return result; }

	// Vérification de l'existance du sommet
	result = sommetEstExist(graphe, somVoisin);
	if (result != RES_OK) { return result; }

	// Vérification de type de l'arete
	result = typeAreteValide(o);
	if (result != RES_OK) { return result; }

	// On vérifie l'existance d'une telle arete
	result = elementExist(graphe->listesAdjacences[somCourant - 1],
			somVoisin - 1);
	if (result != RES_OK) {
		return ARETE_INEXISANTE;
	}

	// On est sur qu'il existe une telle arete, on le supprime
	result = removeElement(&(graphe->listesAdjacences[somCourant - 1]),
			somVoisin - 1);

	// S'il y a une erreur on la retourne tout de suite
	if (result != RES_OK) { return result; }

	// S'il s'agit d'une arete non-orientée
	if (o == 'n') {

		// On vérifie l'existance d'une telle arete
		result = elementExist(graphe->listesAdjacences[somVoisin - 1],
				somCourant - 1);
		if (result != RES_OK) {
			return ARETE_INEXISANTE;
		}

		// A ce phase arete existe bien, on va la supprimer
		result = removeElement(&(graphe->listesAdjacences[somVoisin - 1]),
				somCourant - 1);
		if (result != RES_OK) { return result; }
	}

	return RES_OK;
}


/*
 * Function		:	getAdjacentVertices
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe * graph - graph
 * 					int vertex - vertex number to get it's adjacent vertices
 *
 * Return		:	NULL - if there is nothing, no adjacent vertex
 * 					TypVoisins* list - list of vertices to return
 *
 * Description 	:	give a list of vertices that vertex is adjacent to.
 *
 * Complexity	:	O(1)
 */
TypVoisins* getAdjacentVertices(Graphe* graph, int vertex) {

	// Graph verification
	if (graph == NULL) {
		printf("Attention, graph given is null - getAdjacentVertices\n");
		return NULL;
	}

	// Vertex number could not be negative
	if (vertex < 0) {
		printf("Attention, vertex number is either null "
				"or negative - getAdjacentVertices\n");
		return NULL;
	}

	// Vertex number could not be greater than max number
	if (vertex >= graph->nbMaxSommets) {
		printf("Attention, vertex number is not valid - getAdjacentVertices\n");
		return NULL;
	}

	// It is either null or a list of vertices
	return graph->listesAdjacences[vertex];
}


// Implementation of depth-first search
int depthFirstSearch(Graphe* graph) {

	// Graph verification
	if (graph == NULL) {
		printf("Attention, graph given is null - depthFirstSearch\n");
		return GRAPHE_INEXISTANT;
	}

	if (vertexColor != NULL) {
		free(vertexColor);
	}
	if (vertexFather != NULL) {
		free(vertexFather);
	}

	// No vertex is discovered yet
	vertexColor = (int *) calloc (graph->nbMaxSommets, sizeof(int));

	// No relation defined between vertices yet
	vertexFather = (int *) calloc (graph->nbMaxSommets, sizeof(int));

	int var;

	// For each vertices
	for (var = 0; var < graph->nbMaxSommets; var++) {
		// if vertex is undiscovered
		if (vertexColor[var] == 0) {
			discoverDFS(graph, var);
		}
	}


	free(vertexColor);
	vertexColor = NULL;
	free(vertexFather);
	vertexFather = NULL;

	return RES_OK;
}

// Discover function of depth-first search
int discoverDFS(Graphe* graph, int vertex) {

	// Graph verification
	if (graph == NULL) {
		printf("Attention, graph given is null - discoverDFS\n");
		return GRAPHE_INEXISTANT;
	}

	// Vertex number could not be negative
	if (vertex < 0) {
		printf("Attention, vertex number is either null "
				"or negative - discoverDFS\n");
		return SOMMET_INVALIDE;
	}

	// Vertex number could not be greater than max number
	if (vertex >= graph->nbMaxSommets) {
		printf("Attention, vertex number is not valid - discoverDFS\n");
		return SOMMET_INVALIDE;
	}

	if (vertexColor == NULL || vertexFather == NULL) {
		printf("Attention, please call depthFirstSearch() function\n");
		printf("Don't use this function directly\n");
		return -1;
	}

	// Now this vertex is discovered
	vertexColor[vertex] = 1;
	printf("%d ", vertex + 1);

	TypVoisins * adjacencyList = NULL;
	adjacencyList = getAdjacentVertices(graph, vertex);

	adjacencyList = adjacencyList->voisinSuivant;

	do {

		int adjacent = adjacencyList->voisin;
		if (vertexColor[adjacent] == 0) {
			discoverDFS(graph, adjacent);
		}
		adjacencyList = adjacencyList->voisinSuivant;
	}
	while (adjacencyList->voisin != FIRST_ELEMT_VALUE);

	return RES_OK;
}
/*
 * Function		:	nearestNeighbor
 *
 * Authors		:	IBRAHIMLI Nihat
 *
 * Parameters	:	Graphe graph - the graph
 * 					int root - an arbitrary vertex for to start visiting
 *					int** selectedVertices - an pointer table that these 
 * 										cases has initialised to - 1
 *
 * Return		:	GRAPHE_INEXISTANT - if the graph given is null
 *					MAX_SOMMET_INVALIDE - if the max vertex number is negative or zero
 * 					SOMMET_INVALIDE - if vertex number is not valid
 * 					RAPHE_NOT_COMPLET - if the graph isn't complete
 *					RES_OK if the result is ok
 *
 * Description 	:	find out the shortest path in the graph by nearest neighbor's method
 *
 * Complexity	:	O(v*e) v is number of vertices and e is number of edges
 */
int nearestNeighbor(Graphe* graph, int root, int** selectedVertices) {
	// Graph verification
	int err = grapheEstValide(graph);
	// If there is an error, we get it !
	if (err != RES_OK) { return err; }
	// Vertex verification
	err = sommetEstValide(graph->nbMaxSommets, root);
	if (err != RES_OK) { return err; }

	int i = 0;
	// a temporary vertex
	int vertexTemp;
	int selected = 0;
	double minDistance;
	root = root - 1;
	TypVoisins * adjacencyList = NULL;	
	Stack *stack = NULL;
	initStack(&stack);
	// put the root vertex into the steak
	pushStack(stack,root);	
	// until we get the empty steak
	while(stack->size != 0){		
		// distance is initialised to INFINITY
		minDistance = INFINITY;
		// get the element from steak
		vertexTemp = popStack(stack);
		// insert the nearest neighbor vertex into the selected vertices table
		(*selectedVertices)[i] = vertexTemp;
		// get all edges that leave from this vertex
		adjacencyList = getAdjacentVertices(graph, vertexTemp);		
		// if the graph isn't complete
		if (adjacencyList == NULL){
			printf("\nthe graph isn't complete - nearestNeighbor!\n");
			return GRAPHE_NOT_COMPLET;
		}		
		adjacencyList = adjacencyList->voisinSuivant;			
		// for each these edges
		while(adjacencyList->voisin != -1){
			// the verification of the vertex(adjacencyList->voisin) 								
			selected = vertexColorized(*selectedVertices,adjacencyList->voisin,graph->nbMaxSommets);
			// if the weight of the vertex is less than minDistance and the vertex hasn't been already selected 
			if((adjacencyList->poidsVoisin < minDistance) && !selected){
				// distance is initialised to the weight of the nearest neighbor vertex
				minDistance = adjacencyList->poidsVoisin;
				// the new vertex is initialised to the nearest neighbor vertex
				vertexTemp = adjacencyList->voisin;
			}

			adjacencyList = adjacencyList->voisinSuivant;		
		}
		// if minDistance has changed
		if (minDistance != INFINITY)
		{
			pushStack(stack,vertexTemp);	
		}
		i++;		
	}
	// free stack from memory
	freeStack(&stack);
	return RES_OK;
}

 // check out if a vertex has been already selected
int vertexColorized(int* selected,int vertex,int size)
{
  int i;  
  for(i = 0;i < size;i++){    
  	//if the vertex has been already colorized
    if(selected[i] == vertex){
      return 1;
  	}
  }  
  return 0;
}

/*
 * Function		:	smallestDetour
 *
 * Authors		:	IBRAHIMLI Nihat
 *
 * Parameters	:	Graphe * graph - the pointer graph
 * 					int vertex1 - the first arbitrary vertex 
 * 					int vertex2 - the second arbitrary vertex 
 * 					int vertex3 - the third arbitrary vertex 
 *					int** solution - the pointer table
 *
 * Return		:	GRAPHE_INEXISTANT - if the graph given is null
 *					MAX_SOMMET_INVALIDE - if the max vertex number is negative or zero
 * 					SOMMET_INVALIDE - if vertex number is not valid
 *					RES_OK if the result is ok
 *
 * Description 	:	find out the shortest path in the graph with smaller detour's method
 *
 * Complexity	:	O(v*e) v is number of vertices and e is number of edges
 */
 int smallestDetour(Graphe* graph, int vertex1, int vertex2, int vertex3, int** solution) {
	
	// Graph verification
	int err = grapheEstValide(graph);
	// If there is an error, we get it !
	if (err != RES_OK) { return err; }
	
	// Vertex verification
	err = sommetEstValide(graph->nbMaxSommets, vertex1);
	if (err != RES_OK) { return err; }
	err = sommetEstValide(graph->nbMaxSommets, vertex2);
	if (err != RES_OK) { return err; }
	err = sommetEstValide(graph->nbMaxSommets, vertex3);
	if (err != RES_OK) { return err; }

	vertex1 = vertex1 - 1;
	vertex2 = vertex2 - 1;
	vertex3 = vertex3 - 1;
	// insert the vertices into the array solution (the solutionarray)
	(*solution)[0] = vertex1;
	(*solution)[1] = vertex2;
	(*solution)[2] = vertex3;	

	// distance and minimum distance found
	double distance, distanceMin;

	// the array temporarily used in the instruction
	int* arrayTemp = NULL ;
	arrayTemp = (int *) malloc (sizeof(int) * graph->nbMaxSommets);
	// an array that contains the vertices that have smaller detour
	int* arrayMin = NULL ;
	arrayMin = (int *) malloc (sizeof(int) * graph->nbMaxSommets);
	// j is the vertex non selected
	int j,i;
	// until all vertices have been selected
	while(!allVerticesSelected(*solution,graph->nbMaxSommets)){
		j = 0;
		// distance is initialised to INFINITY
		distanceMin = INFINITY;		
		//for each vertices
		while(j < graph->nbMaxSommets){			
			// if the current the vertex (j) isn't selected
			if (!vertexColorized(*solution,j,graph->nbMaxSommets))
			{	
				// for each vertices selected				
				for (i = 0; i < graph->nbMaxSommets; i++)
				{			
					// if the vertex (i) is selected		
					if ((*solution)[i] != -1)
					{	
						// get new edge between the vertex non selected and the vertices selected
						copyVertexInArray(*solution,&arrayTemp,j,i,graph->nbMaxSommets);
						// compute the new value of distance of detour 
						distance = getPathSize(graph,arrayTemp);						
						// if the distance is greater than the new distance
						if (distanceMin > distance)
						{							
							distanceMin = distance;
							// copy arrayTemp to arrayMin
							copyArray(arrayTemp,&arrayMin,graph->nbMaxSommets);
						}
					}
				}					
			}			
			j++;			
		}		
		copyArray(arrayMin,solution,graph->nbMaxSommets);
	}
	free(arrayTemp);
	free(arrayMin);	
	return RES_OK;
}

// create a copy of an array
void copyArray(int* fromTab, int** toTab, int size){
	int i;
	for (i = 0; i < size; ++i)
	{
		(*toTab)[i] = fromTab[i];
	}
}

// insert the vertex in index +1 of new table and move other values of table in index + 1 
void copyVertexInArray(int* tab, int** result ,int vertex, int index, int size){	
	int i,j = 0;	
	for (i = 0; i < size; ++i)
	{	
		// insert the vertex in index + 1
		if (i == index + 1)
		{
			(*result)[i] = vertex;		
		}
		// move remains values of table in index + 1
		else{
			(*result)[i] = tab[j];
			j++;
		}			
	}
}

// get distance between the vertices that are in "vertices" table 
double getPathSize(Graphe* graph, int* vertices){
	int i;
	double length = 0.0;
	int size = graph->nbMaxSommets;
	for (i = 0; i < size - 1; i++)
	{
		// get weight between the vertex that is in vertices[i] and the next vertex
		if (vertices[i] != -1 && vertices[i+1] != -1 && i+1 != size - 1)
		{
			length += getPoids(graph,vertices[i],vertices[i+1]);		
		}
		if (vertices[i] != -1 && vertices[i+1] != -1 && i+1 == size - 1)
		{
			length += getPoids(graph,vertices[i],vertices[i+1]) + getPoids(graph,vertices[0],vertices[i+1]);		
		}		
		// get weight between the last vertex and the root vertex
		if (vertices[i] != -1 && vertices[i+1] == -1){
			length += getPoids(graph,vertices[i],vertices[0]);		
		}		
	}
	return length;
}

// get weight between fromVertex and toVertex
int getPoids(Graphe* graph, int fromVertex, int toVertex){
	
	TypVoisins * adjacencyList = NULL;	
	adjacencyList = getAdjacentVertices(graph, fromVertex);
	
	while(adjacencyList->voisin != toVertex){
		adjacencyList = adjacencyList->voisinSuivant;
	}
	return adjacencyList->poidsVoisin;
}

 // check out if all vertices are selected
int allVerticesSelected(int* selected,int size)
{
  int i;
  for(i = 0;i < size;i++){    
    if(selected[i] == -1){
      return 0;
  	}
  }
  return 1;
}

/*
 * Function		:	less2Factor
 *
 * Authors		:	IBRAHIMLI Nihat
 *
 * Parameters	:	Graphe graph - the graph
 * 					int root - an arbitrary vertex for to start visiting
 *
 * Return		:	GRAPHE_INEXISTANT - if the graph given is null
 *					MAX_SOMMET_INVALIDE - if the max vertex number is negative or zero
 * 					SOMMET_INVALIDE - if vertex number is not valid
 *					RES_OK if the result is ok
 *
 * Description 	:	find out the shortest path in the graph by a factor of 2 less than the optimal
 *						firstly we compute minimum spanning tree 
 * 							then traversing this tree with Depth-first search (DFS) algo. 	
 *
 * Complexity	:	O(v*e) v is number of vertices and e is number of edges
 */
 int less2Factor(Graphe* graph, int root){
	
	// Graph verification
	int err = grapheEstValide(graph);
	// If there is an error, we get it !
	if (err != RES_OK) { return err; }

	// Vertex verification
	err = sommetEstValide(graph->nbMaxSommets, root);
	if (err != RES_OK) { return err; }

	Graphe* arpm = NULL;
	// create a graph
	err = creation(&arpm, graph->nbMaxSommets);
	
	err = grapheEstValide(arpm);
	// If there is an error, we get it !
	if (err != RES_OK) { return err; }	
	
	// compute minimum spanning tree 	
	err = graphToARPM(graph, arpm, root);
	if (err != RES_OK) { return err; }	

	printf("\nARPM calcule sous un graphe");
	affichageGraphe(arpm);
	printf("\n");

	printf("\nResultat de cycle hamiltonien issu d'un ARPM\n\n");
	// traversing with DFS
	err = depthFirstSearch(arpm);
	freeGraphe(&arpm);
	return RES_OK;
 }

/*
 * Function		:	graphToARPM
 *
 * Authors		:	IBRAHIMLI Nihat
 *
 * Parameters	:	Graphe  graph - the graph
 *				  	Graphe* arpm - the graph which represent minimum spanning tree 
 * 									(recouvrement de poids minimum du graphe)
 * 					int root - an arbitrary vertex for to start visiting
 *
 * Return		:	GRAPHE_INEXISTANT - if the graph given is null
 *					MAX_SOMMET_INVALIDE - if the max vertex number is negative or zero
 * 					SOMMET_INVALIDE - if vertex number is not valid
 *					RES_OK if the result is ok
 *
 * Description 	:	find a minimum spanning tree for a connected weighted undirected graph
 *
 * Complexity	:	O(E log(V)) V is number of vertices and E is number of edges
 */

 int graphToARPM(Graphe* graph, Graphe* arpm, int root){
 	
 	// Graph verification
	int err = grapheEstValide(graph);
	// If there is an error, we get it !
	if (err != RES_OK) { return err; }

	// Graph verification
	err = grapheEstValide(arpm);
	// If there is an error, we get it !
	if (err != RES_OK) { return err; }

	// Vertex verification
	err = sommetEstValide(graph->nbMaxSommets, root);
	if (err != RES_OK) { return err; }

	root = root - 1;
 	
	int i;
 	// create a heap
 	Heap* heap = NULL;
 	initHeap(&heap,graph->nbMaxSommets); 	 	
 	// put all vertices into the heap
 	for (i = 0; i < graph->nbMaxSommets; ++i)
 	{
 		TypHeap elem;
 		elem.vertex = i;
 		elem.predecessorVertex = -1;
 		if (i==root)
 		{
 			elem.weight = 0.0; 		
 		}
 		else
 		{
 			elem.weight = INFINITY; 		
 		}
 		// insert each element into the heap
 		insertElem(heap,elem);
 	} 
 	// until we get the empty heap
 	while(heap->nbMember != 0){
 		TypHeap elem; 
 		// get the minimum edge explored first		 	
 		err = extractMin(heap,&elem); 		 		
 		if(err != RES_OK){
 			return err;
 		}
 		// create the minimum spanning tree (insert the vertices and edges)
 		createTreeARPM(arpm,elem); 	 		
 		TypVoisins * adjacencyList = NULL;
 		// get all edges that leave from this vertex
 		adjacencyList = getAdjacentVertices(graph, elem.vertex);		
 		adjacencyList = adjacencyList->voisinSuivant;
 		// for each of these edges 		
 		while(adjacencyList->voisin != -1){
 			// if the heap contains the vertex and the weight of vertex on the heap is less than that on the graph 			
			if (memberOfHeap(*heap,adjacencyList->voisin) && 
					adjacencyList->poidsVoisin < getWeightOfVertex(*heap,adjacencyList->voisin))
			{
				// set the predecessor of vertex
				err = setPredecessorVertex(heap,adjacencyList->voisin,elem.vertex);
				if (err != RES_OK)
				{
					return err;
				}
				// set the weight of vertex
				err = setWeightOfVertex(heap,adjacencyList->voisin,adjacencyList->poidsVoisin);					
				if (err != RES_OK)
				{
					return err;
				}
			}
			adjacencyList = adjacencyList->voisinSuivant;
 		}
 	}
 	// free heap from memory
 	freeHeap(heap);
 	return RES_OK; 	
 }

// create the minimum spanning tree 
void createTreeARPM(Graphe* arpm, TypHeap elem){
	// insert the vertex
	insertionSommet(arpm,elem.vertex + 1);
	// if the predecessor of vertex has already filled, insert the edge also
	if (elem.predecessorVertex != -1)
	{
		insertionArete(arpm, elem.predecessorVertex + 1, elem.vertex + 1, elem.weight, 'n');
	}	
}

/*******************************************************************
 *
 * Fonction 	: 	freeGraphe
 *
 * Parametres 	: 	Graphe** graphe - le graphe
 *
 * Retour		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 	 				MAX_SOMMET_INVALIDE si le nombre maximum de sommets n'est pas valide
 * 					RES_OK  si le resultat est OK
 *
 * Description 	: 	fonction libere la mémoire d'un graphe. D'abord
 * 					les liste adjacences, ensuite le tableau, et
 * 					enfin le graphe lui-meme.
 *
 *
 * Complexité	:	O(n) n est le nombre max de sommet du graphe
 *
 */

int freeGraphe(Graphe** graphe) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide((*graphe));

	// Si il y a une erreur, on ne continue pas !
	if (result != RES_OK) {
		if (result == GRAPHE_INEXISTANT) {
			fprintf(stderr, "freeGraphe - graphe inexistant");
		}
		return result;
	}

	int i;
	// On libere tous les listes
	for (i = 0; i < (*graphe)->nbMaxSommets; i++) {

		if ((*graphe)->listesAdjacences[i] != NULL) {
			result = freeListe(&((*graphe)->listesAdjacences[i]));
			if (result != RES_OK) { return result; }
		}
	}

	free((*graphe)->listesAdjacences);
	(*graphe)->listesAdjacences = NULL;

	free((*graphe));
	(*graphe) = NULL;

	return RES_OK;

}

/*******************************************************************
 *
 * Fonction 	: 	affichageGraphe
 *
 * Parametres 	: 	Graphe* graphe - le graphe courant
 *
 * Retour		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 	 				MAX_SOMMET_INVALIDE si le nombre maximum de sommets n'est pas valide
 * 					RES_OK  si le resultat est OK
 *
 * Description 	: 	fonction affiche un graphe
 *
 *
 * Complexité	:	O(n) n est le nombre max de sommet du graphe
 *
 */

int affichageGraphe(Graphe* graphe) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graphe);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	int i;

	printf("\n# nombre maximum de sommets\n");
	printf("%d\n", graphe->nbMaxSommets);
	printf("# sommets : (voisins/poids)\n");

	for (i = 0; i < graphe->nbMaxSommets; i++) {

		if (graphe->listesAdjacences[i] != NULL) {
			if (i < 9) {	printf(" %d: ", i + 1); }
			else { printf("%d: ", i + 1); }
			printListe(graphe->listesAdjacences[i]);
		}
		printf("\n");
	}

	return RES_OK;
}


// Enregistre un graphe dans un fichier
int writeGrapheToFile(Graphe* graphe, char* filePath) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graphe);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	FILE *file = NULL;
	file = fopen(filePath, "w");

	fprintf(file,"%s","# nombre maximum de sommets\n"); /*writes*/
	fprintf(file,"%d", graphe->nbMaxSommets);
	fprintf(file, "\n");
	fprintf(file, "%s", "# sommets : (voisins/poids)\n");

	int i = 0;
	for (i = 0; i < graphe->nbMaxSommets; i++) {

		// On vas ajouter celle qui sont existe
		if (graphe->listesAdjacences[i] != NULL) {

			fprintf(file, "%d: ", i + 1);
			// On ajoute la liste des arete pour ce sommet
			writeListToFile(graphe->listesAdjacences[i], file);
			if (i != graphe->nbMaxSommets - 1) {
				fprintf(file, "\n");
			}
		}
	}


	fclose(file);

	return RES_OK;
}

/*******************************************************************
 *
 * Fonction 	: 	grapheEstValide
 *
 * Parametres 	: 	Graphe* graphe - le graphe
 *
 * Retour		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 	 				MAX_SOMMET_INVALIDE si le nombre maximum de sommets n'est pas valide
 * 					RES_OK  si le resultat est OK
 *
 * Description 	: 	fonction vérifie si un graphe donnee est valide, est existe ou pas.
 *
 *
 * Complexité	:	O(1)
 *
 */

int grapheEstValide(Graphe* graphe) {

	// Verification de graphe
	if (graphe == NULL) {
		fprintf(stderr, "\ngrapheEstValide - graphe donne est null !\n");fprintf(stderr, "\ngrapheEstValide - graphe donne est null !\n");
		return GRAPHE_INEXISTANT;
	}

	// Vérification de nombre de max de sommet
	if (graphe->nbMaxSommets <= 0) {
		fprintf(stderr, "\ngrapheEstValide - nombre max sommet est negative ou null !\n");
		return MAX_SOMMET_INVALIDE;
	}

	// Verification de tableau de liste d'adjacences
	if (graphe->listesAdjacences == NULL) {
		fprintf(stderr, "\ngrapheEstValide - graphe donne est null !\n");
		return GRAPHE_INEXISTANT;
	}

	return RES_OK;
}


/*******************************************************************
 *
 * Fonction 	: 	sommetEstValide
 *
 * Parametres 	: 	int nbMaxSommets - nombre max de sommets d'un graphe
 * 					int sommet - le numero de sommet à vérifier
 *
 * Retour		:	SOMMET_INVALIDE si le sommet est negative ou
 * 									superieur de nbMaxSommets
 * 					RES_OK  si le resultat est OK
 *
 * Description 	: 	fonction vérifie si un numero sommets donnee
 * 					peut etre valide, pour en inserer par ex.
 *
 *
 * Complexité	:	O(1)
 *
 */

int sommetEstValide(int nbMaxSommets, int sommet) {

	// Pas de sommet negative
	if (sommet <= 0) {
		return SOMMET_INVALIDE;
	}

	// Pas de numero sommet plus grand que maximum
	if (sommet > nbMaxSommets) {
		return SOMMET_INVALIDE;
	}

	return RES_OK;
}


/*******************************************************************
 *
 * Fonction 	: 	sommetEstExist
 *
 * Parametres 	: 	Graphe* graphe - le graphe
 * 					int sommet - le sommet à vérifier
 *
 * Retour		:	GRAPHE_INEXISTANT si le graphe n'existe pas
 * 	 				MAX_SOMMET_INVALIDE si le nombre maximum de sommets n'est pas valide
 * 					RES_OK  si le resultat est OK
 *
 * Description 	: 	fonction vérifie si un numero sommets donne
 * 					existe déjà dans le graphe donne
 *
 *
 * Complexité	:	O(1)
 *
 */
int sommetEstExist(Graphe* graphe, int sommet) {

	int result = 0;

	// Vérification de graphe
	result = grapheEstValide(graphe);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	// Verification de graphe et le sommet
	result = sommetEstValide(graphe->nbMaxSommets, sommet);

	// Si il y a une erreur, on continue pas !
	if (result != RES_OK) { return result; }

	return RES_OK;
}


/*******************************************************************
 *
 * Fonction 	: 	poidsEstValide
 *
 * Parametres 	: 	double poids - le poids à vérifier
 *
 * Retour		:	POIDS_INVALIDE si le poids n'est pas valide
 *
 * Description 	: 	fonction vérifie si un poids est valide
 * 					ou pas.
 *
 * Complexité	:	O(1)
 *
 */
int poidsEstValide(double poids) {

	// Vérification du poids
	if (poids <= 0.0) {
		fprintf(stderr, "\npoidsEstValide - poids donnee est negative !\n");
		return POIDS_INVALIDE;
	}

	return RES_OK;
}

/*******************************************************************
 *
 * Fonction 	: 	typeAreteValide
 *
 * Parametres 	: 	char o - type arete à vérifier
 *
 * Retour		:	TYPE_ARETE_INVALID si le type d'arete n'est pas valide
 * 					RES_OK si le type est bon.
 *
 * Description 	: 	fonction vérifie si un type donne est valide
 * 					ou pas.
 *
 * Complexité	:	O(1)
 *
 */
int typeAreteValide(char type) {

	if (type != 'o' && type != 'n') {
		return TYPE_ARETE_INVALID;
	}

	return RES_OK;
}

// Tests whether there is an edge between vertices
int isAdjacent(Graphe* graph, int vertex0, int vertex1) {

	// Graph
	if (graph == NULL) {
		printf("\nGraph given is null - getEdgeCost\n");
		return GRAPHE_INEXISTANT;
	}

	// Vertex from
	if (vertex0 < 0 || vertex0 >= graph->nbMaxSommets) {
		printf("\nFirst vertex number is not valid - getEdgeCost\n");
		return SOMMET_INVALIDE;
	}

	// Vertex to
	if (vertex1 < 0 || vertex1 >= graph->nbMaxSommets) {
		printf("\nSecond vertex number is not valid - getEdgeCost\n");
		return SOMMET_INVALIDE;
	}

	// Get list
	TypVoisins * list = NULL;
	list = graph->listesAdjacences[vertex0]->voisinSuivant;

	int found = -1;

	// Try to find vertex to
	while (list->voisin != FIRST_ELEMT_VALUE) {
		if (list->voisin == vertex1) {
			found = 0;
		}
		list = list->voisinSuivant;
	}


	return (found == 0) ? IS_ADJACENT : IS_NOT_ADJACENT;
}


/*
 * Function		:	getEdgeCost
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe * graph - graph
 * 					int _ first vertex
 * 					int _ second vertex
 *
 * Return		:	GRAPHE_INEXISTANT - If graph is null
 * 					SOMMET_INVALIDE - if one of the vertex is not valid
 * 					double _ the cost of the edge
 *
 * Description 	:	Get the cost of edge between vertices
 *
 * Complexity	:	O(n) - n is the number of adjacent vertices to the first one
 */
double getEdgeCost(Graphe* graph, int vertex0, int vertex1) {

	// Graph
	if (graph == NULL) {
		printf("\nGraph given is null - getEdgeCost\n");
		return GRAPHE_INEXISTANT;
	}

	// Vertex from
	if (vertex0 < 0 || vertex0 >= graph->nbMaxSommets) {
		printf("\nFirst vertex number is not valid - getEdgeCost\n");
		return SOMMET_INVALIDE;
	}

	// Vertex to
	if (vertex1 < 0 || vertex1 >= graph->nbMaxSommets) {
		printf("\nSecond vertex number is not valid - getEdgeCost\n");
		return SOMMET_INVALIDE;
	}

	// Get list
	TypVoisins * list = NULL;
	list = graph->listesAdjacences[vertex0]->voisinSuivant;

	double edge = 0.0;

	// Try to find vertex to
	while (list->voisin != FIRST_ELEMT_VALUE) {

		// Found, get it.
		if (list->voisin == vertex1) {
			// Don't need to continue
			edge = list->poidsVoisin;
			break;
		}
		list = list->voisinSuivant;
	}

	return edge;
}



/*
 * Function		:	getExactTSPSolution
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe * graph - graph to use
 *
 * Return		:	GRAPHE_INEXISTANT - If graph is null
 * 					RES_OK - it's ok
 *
 * Description 	:	find the exact solution to visit all vertices of a graph
 * 					with the minimum length possible. This function must be
 * 					used while a graph has less than 10 vertices. Otherwise
 * 					it takes much time, much memory as a result of it's
 * 					complexity
 *
 * Complexity	:	O(N!) - n is the number of vertices
 */
int getExactTSPSolution(Graphe * graph) {

	// Graph verification
	if (graph == NULL) {
		printf("\nGraph is null - getExactTSPSolution\n");
		return GRAPHE_INEXISTANT;
	}

	// Get number of vertices
	int size = graph->nbMaxSommets;

	// Must be used for little graphs
	if (size >= 10) {
		printf("\nPlease use this function when number "
				"of vertices is less than 10. It's not a good method otherwise.\n");
		return -1;
	}

	double ** matrix;
	printf("\nPlease wait...");
	graphToMatrix(graph, &matrix);

	Stack * allVertex = NULL;
	initStack(&allVertex);

	int var, var2;
	for (var = 0; var < size; var++) {
		if (graph->listesAdjacences[var] != NULL) {
			pushStack(allVertex, var+1);
		}
	}

	List list = NULL, listTemp = NULL;

	// Enumerate all cycles, stock them in the list
	enumereCycles(&list, 0, allVertex);
	listTemp = list;

	double minimumCycleLength = INFINITY;
	double maximumCycleLength = 0;

	int minimumCycle = 0;
	int maximumCycle = 0;

	double distance = 0.0;

	// For each cycle found
	while (listTemp->next != NULL) {

		int path = listTemp->value;

		// Calculate number of digits in it (= number of vertices)
		int numberOfDigits = (int) (1 + log10(path));

		int modulo = 10;
		distance = 0.0;

		// Calculate length of the cycle
		for (var2 = 1; var2 < numberOfDigits; var2++) {

			int firstVertex = path % modulo;
			path /= 10;
			int secondVertex = path % modulo;

			distance += matrix[firstVertex - 1][secondVertex - 1];
		}

		if (distance > maximumCycleLength) {
			maximumCycleLength = distance;
			maximumCycle = listTemp->value;
		}

		// Found new cycle much more better
		if (distance < minimumCycleLength) {
			minimumCycleLength = distance;
			minimumCycle = listTemp->value;
		}

		listTemp = listTemp->next;
	}

	printf("\nThe best solution is : %d with a length of %f",
			minimumCycle, minimumCycleLength);

	printf("\nThe worst solution is : %d with a length of %f",
			maximumCycle, maximumCycleLength);

	freeSlist(list);

	// Free all memory used
	freeMatrix(&matrix, size);
	printf("\n\n");
	freeStack(&allVertex);

	return RES_OK;
}


/*
 * Function		:	enumereCycles
 *
 * Authors		:	Fouad HANNA & BAYRAMOV Matin,
 *
 * Parameters	:	Stack *listeDeParcours - to stock all cycles
 * 					int prefix - the prefix of a cycle
 * 					Stack *v - set of all vertices
 *
 * Return		:	RES_OK and add all cycles to the first parameter
 *
 * Description 	:	find all different possible ways to visit all vertices
 * 					by passing just one time. Add all them to the first
 * 					parameter
 *
 * Complexity	:	O(N!) - n is the number of vertices
 */
int enumereCycles(List * listeDeParcours, int prefix, Stack* v) {

	// There is only one vertex not seen yet
	if (v->size == 1) {

		// Add it to prefix
		prefix = prefix * 10 + v->items[0];

		// Save this one into the set
		(*listeDeParcours) = addBeginSlistElement(*listeDeParcours, prefix);

		return RES_OK;
	}

	// Get size of vertices
	int size = (int) v->size, var;

	// For each one
	for (var = 0; var < size; var++) {

		// Create a new set without current vertex
		Stack *cloned = NULL;
		cloneStack(v, &cloned);
		popStackItem(cloned, v->items[var]);

		// Add it to prefix
		int newPrefix = prefix * 10 + v->items[var];

		// Call to do others
		enumereCycles(listeDeParcours, newPrefix, cloned);

		// Not need any more
		freeStack(&cloned);
	}

	return RES_OK;
}

/*
 * Function		:	graphToMatrix
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe* graph - graph to convert
 * 					double *** matrix - matrix pointer
 *
 * Return		:	GRAPHE_INEXISTANT - if graph is null
 * 					PROBLEME_MEMOIRE - if there is a memory problem
 * 					RES_OK - it's OK
 *
 * Description 	:	Convert a graph to a matrix
 *
 * Complexity	:	O(n) - n is the number of elements in the list
 */
int graphToMatrix(Graphe* graph, double ***matrix) {

	// Verify graph
	if (graph == NULL) {
		printf("\nGraph is null - graphToMatrix\n");
		return GRAPHE_INEXISTANT;
	}

	// Allocating for matrix
	(*matrix) = (double **) malloc (sizeof (double *) * graph->nbMaxSommets);

	// Verification
	if ((*matrix) == NULL) {
		printf("\nMemory PROBLEM - graphToMatrix\n");
		return PROBLEME_MEMOIRE;
	}

	int var, var2;

	// For each vertex of graph
	for (var = 0; var < graph->nbMaxSommets; var++) {

		// Create matrix line
		(*matrix)[var] = (double *) malloc (sizeof (double) * graph->nbMaxSommets);

		// Memory verification
		if ((*matrix)[var] == NULL) {
			printf("\nMemory PROBLEM - graphToMatrix\n");
			return PROBLEME_MEMOIRE;
		}

		// Initialize to zero
		for (var2 = 0; var2 < graph->nbMaxSommets; var2++) {
			(*matrix)[var][var2] = 0.0;
		}
	}

	// Fore each graph vertex
	for (var = 0; var < graph->nbMaxSommets; var++) {

		// Get it's target vertices
		TypVoisins * list = NULL;
		list = graph->listesAdjacences[var];

		if (list != NULL) {

			// For each target
			while (list->voisinSuivant->voisin != FIRST_ELEMT_VALUE) {
				list = list->voisinSuivant;

				int vertex = list->voisin;
				double distance = list->poidsVoisin;

				// Define matrix value for this vertices
				(*matrix)[var][vertex] = distance;
			}
		}

	}

	return RES_OK;
}


/*
 * Function		:	algorithmChristofides
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe* graph - graph
 *
 * Return		:	GRAPHE_INEXISTANT - if graph is null
 * 					RES_OK - it's OK
 *
 * Description 	:	Implement Christofides algorithm
 *
 * Complexity	:
 */
int algorithmChristofides(Graphe* graph) {

	// Graph verification
	if (graph == NULL) {
		printf("\nGraph is null - algorithmChristofides\n");
		return GRAPHE_INEXISTANT;
	}

	// Used to treat function's return value
	int resReturn = 0;

	// Get ARPM graph
	Graphe * graphArpm = NULL;
	creation(&graphArpm, graph->nbMaxSommets);
	resReturn = graphToARPM(graph, graphArpm, 1);

	if (resReturn != RES_OK) {
		printf("\nProblem occurred while calling graphToARPM "
				"- algorithmChristofides\n");
		return resReturn;
	}

	// Array to stock odd vertices
	int * oddOrEvenDegree = NULL;

	resReturn = createIntArray(&oddOrEvenDegree, graphArpm->nbMaxSommets);

	if (resReturn != RES_OK) {
		freeGraphe(&graphArpm);
		return resReturn;
	}

	// Get whether vertices are odd or even degree
	oddOrEvenDegreeVertex(graphArpm, oddOrEvenDegree);

	int * oddOrEvenDegreeCopy = NULL;
	cloneIntArray(oddOrEvenDegree, &oddOrEvenDegreeCopy, graphArpm->nbMaxSommets);


	if (DEBUG_MODE == 0) {
		printIntArray(oddOrEvenDegree, graphArpm->nbMaxSommets);
	}

	int from = 0, to = 0;
	int vertexA = 0, vertexB = 0;
	double edge = 0.0;

	double costMinimum = INFINITY;

	int minimumTJoinFound = 0;

	affichageGraphe(graphArpm);
	while (minimumTJoinFound == 0) {

		minimumTJoinFound = 1;
		costMinimum = INFINITY;

		from = 0; to = 0;
		while (from < graphArpm->nbMaxSommets) {

			// Don't need even degree vertices
			if (oddOrEvenDegree[from] == 0) { from++; continue; }

			to = from + 1;

			while (to < graphArpm->nbMaxSommets) {

				// Don't need even degree vertices
				if (oddOrEvenDegree[to] == 0) { to++; continue; }

					edge = getEdgeCost(graph, from, to);

					if (edge < costMinimum) {
						costMinimum = edge;
						vertexA = from;
						vertexB = to;
						minimumTJoinFound = 0;
					}
				to++;
			}
			from++;
		}

		if (minimumTJoinFound == 0) {

			// Don't need to test them any more
			oddOrEvenDegree[vertexA] = 0;
			oddOrEvenDegree[vertexB] = 0;

			insertionArete(graphArpm, vertexA+1, vertexB+1, costMinimum, 'n');

			printf("\nCouplage minimum : (%d, %d) -> %f", vertexA+1, vertexB+1, costMinimum);
		}
	}
	printf("\n");

	affichageGraphe(graphArpm);

	int var0 = 0;
	printf("\nRaccourcir la tournee pour les sommets : ");
	for (var0 = 0; var0 < graphArpm->nbMaxSommets; var0++) {

		// Don't need even degree vertices
		if (oddOrEvenDegreeCopy[var0] == 0) { continue; }

		shortenThePath(graph, graphArpm, var0);
	}

	printf("\n");

	free(oddOrEvenDegree);
	free(oddOrEvenDegreeCopy);
	freeGraphe(&graphArpm);

	return RES_OK;
}

/*
 * Function		:	raccourcirLaTrounee
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe* graph - graph
 * 					Graphe* arpm - ARPM
 *
 * Return		:	GRAPHE_INEXISTANT - if graph is null
 * 					RES_OK - it's OK
 *
 * Description 	:	Try to shorten a road if the path passes more
 * 					than one time by the vertex.
 *
 * Complexity	:
 */
int shortenThePath(Graphe* graph, Graphe* arpm, int vertex) {

	if (graph == NULL || arpm == NULL) {
		printf("\nGraph given is null - raccourcirLaTrounee\n");
		return GRAPHE_INEXISTANT;
	}

	if (vertex < 0 || vertex >= arpm->nbMaxSommets) {
		printf("\nVertex given is not valid - raccourcirLaTrounee\n");
		return SOMMET_INVALIDE;
	}

	// Get number of outgoing edges
	int outGoingEdges = countOutgoingEdges(arpm, vertex);

	// Nothing to do if it is 1 or 2
	if (outGoingEdges < 3) {
		return RES_OK;
	}

	printf("%d ", vertex+1);

	// Array to stock odd vertices
	int * arrayVertex = NULL;

	int resReturn = createIntArray(&arrayVertex, outGoingEdges);

	if (resReturn != RES_OK) {
		return resReturn;
	}

	// Get list
	TypVoisins * list = NULL;
	list = arpm->listesAdjacences[vertex]->voisinSuivant;
	int var = 0;
	while (list->voisin != FIRST_ELEMT_VALUE) {
		arrayVertex[var] = list->voisin;
		list = list->voisinSuivant;
		var++;
	}

	//int vertexA = 0, vertexB = 0;
	int var0 = 0, var1 = 0;

	double edge = 0.0;

	for (var0 = 0; var0 < outGoingEdges; var0++) {

		for (var1 = var0+1; var1 < outGoingEdges; var1++) {

			edge = getEdgeCost(graph, arrayVertex[var0], arrayVertex[var1]);
			if (edge < 10) { }

//			printf("\ntournee (%d, %d) -> %.1f", arrayVertex[var0], arrayVertex[var1], edge);
		}
	}

	free(arrayVertex);

	return RES_OK;
}

/*
 * Function		:	countOutgoingEdges
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe* graph - graph
 * 					int vertex - vertex to count number of outgoing edges
 *
 * Return		:	GRAPHE_INEXISTANT - if graph is null
 * 					int _ - number of outgoing vertex
 *
 * Description 	:	Count and return number of outgoing edges
 *
 * Complexity	:	O(n) - n is the number of outgoing edges
 */
int countOutgoingEdges(Graphe * graph, int vertex) {

	// Graph must be exist
	if (graph == NULL) {
		printf("\nGraph given is null - countOutgoingEdges\n");
		return GRAPHE_INEXISTANT;
	}

	// Invalid vertex given ? so zero outgoing edge
	if (vertex < 0 || vertex >= graph->nbMaxSommets) {
		printf("\nVertex given was not valid - countOutgoingEdges\n");
		return 0;
	}

	return sizeOfElements(graph->listesAdjacences[vertex]) - 1;
}

/*
 * Function		:	countIncomingEdges
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe* graph - graph
 * 					int vertex - vertex to count number of incoming edges
 *
 * Return		:	GRAPHE_INEXISTANT - if graph is null
 * 					int _ - number of outgoing vertex
 *
 * Description 	:	Count and return number of incoming edges
 *
 * Complexity	:	O(n) - n is the number of incoming edges
 */
int countIncomingEdges(Graphe * graph, int vertex) {

	// Graph must be exist
	if (graph == NULL) {
		printf("\nGraph given is null - countOutgoingEdges\n");
		return GRAPHE_INEXISTANT;
	}

	// Invalid vertex given ? so zero outgoing edge
	if (vertex < 0 || vertex >= graph->nbMaxSommets) {
		printf("\nVertex given was not valid - countOutgoingEdges\n");
		return 0;
	}

	// Must be implemented in case of need
	return RES_OK;
}


/*
 * Function		:	oddOrEvenDegreeVertex
 *
 * Authors		:	BAYRAMOV Matin
 *
 * Parameters	:	Graphe* graph - graph
 * 					int vertices - array to stock result
 *
 * Return		:	GRAPHE_INEXISTANT - if graph is null
 * 					ARRAY_NULL - if the given array is null
 *
 * Description 	:	Define whether all vertices of a graph are
 * 					odd (1) degree or even (0) degree. It depends
 * 					on the number of outgoing vertices.
 *
 * Complexity	:	O(n2) - n is the number of vertices
 */
int oddOrEvenDegreeVertex(Graphe * graph, int * vertices) {

	// Graph must be exist
	if (graph == NULL) {
		printf("\nGraph is null - getOddDegreeVertices\n");
		return GRAPHE_INEXISTANT;
	}

	// Array must be created
	if (vertices == NULL) {
		printf("\nArray given is null - getOddDegreeVertices\n");
		return ARRAY_NULL;
	}

	int var;

	for (var = 0; var < graph->nbMaxSommets; var++) {

		// Get number of outgoing edges
		int outGoingEdges = countOutgoingEdges(graph, var);

		// All is even
		vertices[var] = 0;

		// Number of outgoing edges is odd
		if (outGoingEdges % 2 == 1) {
			vertices[var] = 1;
		}
	}

	return RES_OK;
}
